using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace LeanUi.ImageBundle
{
    internal class DecreasingHeightComparator : Comparer<ImageRect>
    {
        public override int Compare(ImageRect a, ImageRect b)
        {
            int c = b.Height - a.Height;
            // If we encounter equal heights, use the name to keep things deterministic.
            return (c != 0) ? c : b.Name.CompareTo(a.Name);
        }
    }

    internal class DecreasingWidthComparator : Comparer<ImageRect>
    {
        public override int Compare(ImageRect a, ImageRect b)
        {
            int c = b.Width - a.Width;
            // If we encounter equal heights, use the name to keep things deterministic.
            return (c != 0) ? c : b.Name.CompareTo(a.Name);
        }
    }

    public class VariedSizeArrangingStrategy : IArrangingStrategy
    {
        /**
          * Arranges the images to try to decrease the overall area of the resulting
          * bundle. This uses a strategy that is basically Next-Fit Decreasing Height
          * Decreasing Width (NFDHDW). The rectangles to be packed are sorted in
          * decreasing order by height. The tallest rectangle is placed at the far
          * left. We attempt to stack the remaining rectangles on top of one another to
          * construct as many columns as necessary. After finishing each column, we
          * also attempt to do some horizontal packing to fill up the space left due to
          * widths of rectangles differing in the column.
          */
        public virtual Size ArrangeImages(IList<ImageRect> rects)
        {
            if (!rects.Any())
            {
                return new Size(0, 0);
            }

            // Create a list of ImageRects ordered by decreasing height used for constructing columns.
            var rectsOrderedByHeight = rects.OrderByDescending(ir => ir.Height).ToList();

            // Create a list of ImageRects ordered by decreasing width used for packing individual columns.
            var rectsOrderedByWidth = rects.OrderByDescending(ir => ir.Width).ToList();

            // Place the first, tallest image as the first column.
            var first = rectsOrderedByHeight.First();
            first.SetPosition(0, 0);

            // Setup state for laying things cumulatively.
            int curX = first.Width;
            int colH = first.Height;
            int n = rectsOrderedByHeight.Count;

            for (int i = 1; i < n; i++)
            {
                // If this ImageRect has been positioned already, move on.
                if (rectsOrderedByHeight[i].HasBeenPositioned)
                {
                    continue;
                }

                int colW = 0;
                int curY = 0;

                var rectsInColumn = new List<ImageRect>();
                for (int j = i; j < n; j++)
                {
                    ImageRect current = rectsOrderedByHeight[j];
                    // Look for rects that have not been positioned with a small enough
                    // height to go in this column.
                    if (!current.HasBeenPositioned && (curY + current.Height) <= colH)
                    {
                        // Set the horizontal position here, the top field will be set in
                        // arrangeColumn after we've collected a full set of ImageRects.
                        current.SetPosition(curX, 0);
                        colW = Math.Max(colW, current.Width);
                        curY += current.Height;

                        // Keep the ImageRects in this column in decreasing order by width.

                        int pos = rectsInColumn.BinarySearch(current, new DecreasingWidthComparator());

                        if (pos > 0) throw new Exception("Should not happen");

                        rectsInColumn.Insert(-1 - pos, current);
                    }
                }

                // Having selected a set of ImageRects that fill out this column vertical,
                // now we'll scan the remaining ImageRects to try to fit some in the
                // horizontal gaps.
                if (rectsInColumn.Any())
                {
                    arrangeColumn(rectsInColumn, rectsOrderedByWidth);
                }

                // We're done with that column, so move the horizontal accumulator by the
                // width of the column we just finished.
                curX += colW;
            }

            return new Size(curX, colH);
        }

        /**
           * Companion method to {@link #arrangeImages()}. This method does a best
           * effort horizontal packing of a column after it was packed vertically. This
           * is the Decreasing Width part of Next-Fit Decreasing Height Decreasing
           * Width. The basic strategy is to sort the remaining rectangles by decreasing
           * width and try to fit them to the left of each of the rectangles we've
           * already picked for this column.
           * 
           * @param rectsInColumn the ImageRects that were already selected for this
           *          column
           * @param remainingRectsOrderedByWidth the sub list of ImageRects that may not
           *          have been positioned yet
           */
        private void arrangeColumn(IList<ImageRect> rectsInColumn, IList<ImageRect> remainingRectsOrderedByWidth)
        {
            ImageRect first = rectsInColumn[0];

            int columnWidth = first.Width;
            int curY = first.Height;

            // Skip this first ImageRect because it is guaranteed to consume the full
            // width of the column.
            for (int i = 1, m = rectsInColumn.Count; i < m; i++)
            {
                ImageRect r = rectsInColumn[i];
                // The ImageRect was previously positioned horizontally, now set the top
                // field.
                r.SetPosition(r.Left, curY);
                int curX = r.Width;

                // Search for ImageRects that are shorter than the left most ImageRect and
                // narrow enough to fit in the column.
                for (int j = 0, n = remainingRectsOrderedByWidth.Count; j < n; j++)
                {
                    ImageRect current = remainingRectsOrderedByWidth[j];
                    if (!current.HasBeenPositioned
                        && (curX + current.Width) <= columnWidth
                        && (current.Height <= r.Height))
                    {
                        current.SetPosition(r.Left + curX, r.Top);
                        curX += current.Width;
                    }
                }

                // Update the vertical accumulator so we'll know where to place the next
                // ImageRect.
                curY += r.Height;
            }
        }
    }
}